package RBTree;

import java.util.*;

/**
 * 红黑树
 * 每条支路的黑色节点个数相同，
 * 俩个红色节点不能连着
 * 叶子节点一定是黑色 null也记为黑色 对于左右都为null的节点可以为黑也可以为红
 * 每个节点不是黑就是红
 * 最长路径最多是最短路径的俩被
 */
public class RBTree {
    static class Node {
        Node left = null;
        Node right = null;
        Node parent = null;
        //将节点默认为红色是因为红色的话只会右俩个红色的节点连着这一个不符合红黑树的性质，接着再调整节点颜色
        //而如果默认的是黑色那么就一定会影响红黑树的平衡，且会要新增节点，因为你即使吧父类对应的左右俩节点都改为黑
        //但是这个时候你的树还是不平衡，黑色节点树不会相同
        int val;
        COLOR color = COLOR.RED;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node root = null;

    //红黑树的插入
    public boolean push(int val) {
        Node node = new Node(val);
        if (root == null) {
            root = node;
            root.color = COLOR.BLACK;
            return true;//只有一个
        }
        //找到合适的null位置
        Node tmp = root;
        Node parent = root;
        while (tmp != null) {
            if (val < tmp.val) {
                parent = tmp;
                tmp = tmp.left;
            } else if (val > tmp.val) {
                parent = tmp;
                tmp = tmp.right;
            } else {//这里要去重
//                System.out.println("val已经存在");
                return false;
            }
        }
        //插入
        if (val > parent.val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        tmp = node;
        tmp.parent = parent;//连接起根节点

        Node cur = tmp;
        parent = cur.parent;
        //修改颜色 若被插入的节点为黑色就不用更改颜色
        while (parent != null  && parent.color == COLOR.RED) {//叶子节点一定是黑色的，那么也就是插入的节点的父节点一定是红色
            Node grandfather = parent.parent;
            if (parent == grandfather.left) {//具体的插入分俩种情况
                Node uncle = grandfather.right;

                if (uncle != null && uncle.color == COLOR.RED) {//情况1 uncle存在并且为红色
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandfather.color = COLOR.RED;

                    cur = grandfather;//继续向上更改
                    parent = cur.parent;
//                    if (grandfather.parent != null && grandfather.parent.color == COLOR.RED) {//再看grandfather的父节点的颜色
//                        //为红色需要继续向上 因为为红色说明上面一定还有节点
//                    } else if (grandfather.parent == null || grandfather.parent.color == COLOR.BLACK) {//最次到根就会推出
//                        //grandfather == null || grandfather == BLACK 这种情况可以直接退出循环
//                        // 如果grandfather.parent = null会出现root等于红色的情况，那么就需要自己手动置为BLACK
//                    }
                } else {// uncle == null || uncle.color == BLACK 情况2 3
                    //arent.right == cur
                    if (parent.right == cur) {//先对parent进行左旋,在进行cur右旋
                        rotateLeft(parent);
                        Node tmpP = parent;
                        parent = cur;
                        cur = tmpP;
                    }
                    //parent.left == cur 对parent进行左旋
                    rotateRight(grandfather);
                    parent.color = COLOR.BLACK;
                    grandfather.color = COLOR.RED;


                }
            } else {//parent == grandfather.right
                Node uncle = grandfather.left;//分三种情况
                if (uncle != null && uncle.color == COLOR.RED) {//uncle 存在且为红
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandfather.color = COLOR.RED;

                    if (grandfather.parent == null || grandfather.parent.color == COLOR.BLACK) {
                        //为黑色或者为空就能推出循环，这时已经平衡了
                        break;
                    } else {//为存在且为红色，说明上面必定还有节点，那么就需要继续去更改
                        cur = grandfather;
                        parent = cur.parent;
                    }
                } else {//uncle为空或者是为黑色，那么就绪要用到旋转
                    if (parent.left == cur) {//先右旋parent再左旋cur
                        rotateRight(parent);
//                        parent = cur;//这个时候cur所在位置才是需要旋转的
                        Node tmpP = parent;
                        parent = cur;
                        cur = tmpP;
                    }
                    rotateLeft(grandfather);//parent.right == cur这个情况
                    grandfather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                }
            }
        }

        root.color = COLOR.BLACK;//以防万一可能改了root颜色
        return true;
    }

    //按层来打印树 会将空节点几位null
    public List<List<String>> levelOrder(Node root) {
        List<List<String>> arr = new LinkedList<>();
        if (root == null) {
            return arr;
        } else {
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);

            while (!queue.isEmpty()) {
                int size = queue.size();

                LinkedList tmpL;
                for (tmpL = new LinkedList(); size != 0; --size) {
                    Node tmp = (Node) queue.poll();
                    if (tmp != null) {
//                        tmpL.add("" + tmp.val);
                        tmpL.add("{" + tmp.val +" "+tmp.color +"}");
                        queue.offer(tmp.left);
                        queue.offer(tmp.right);
                    } else {
                        tmpL.add("null");
                    }
                }

                arr.add(tmpL);
            }

            return arr;
        }
    }

    private void rotateRight(Node parent) {
        Node subL = parent.left;
        Node subLR = subL.right;
        //旋转
        subL.right = parent;

        Node parentH = parent.parent;
        parent.parent = subL;

        parent.left = subLR;
        if (subLR != null) {
            subLR.parent = parent;
        }

        if (parent == root) {
            root = subL;
            subL.parent = null;
        } else {//parent不为根
            if (parentH.left == parent) {
                parentH.left = subL;
                subL.parent = parentH;
            } else {
                parentH.right = subL;
                subL.parent = parentH;
            }
        }
    }

    private void rotateLeft(Node parent) {
        //记录节点
        Node subR = parent.right;
        Node subRL = subR.left;

        //旋转
        subR.left = parent;

        Node parentH = parent.parent;
        parent.parent = subR;

        parent.right = subRL;
        if (subRL != null) {//可能parent没有左节点
            subRL.parent = parent;
        }

        if (parent == root) {//那么curR就是新的根节点
            root = subR;
            subR.parent = null;
        } else {
            if (parentH.left == parent) {
                parentH.left = subR;//连接起新的根
                subR.parent = parentH;
            } else {
                parentH.right = subR;
                subR.parent = parentH;
            }
        }
    }

    //获取树的高度
    public int getHeight(Node root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

    public List<Integer> arr = new ArrayList<Integer>();
    //中序遍历
    public void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);

    }
    public void inOrder_getArr(Node root) {
            Stack<Node> stack = new Stack<>();
            Node cur = root;
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.add(cur);
                    cur = cur.left;
                }
                //回退到上一个右节点
                Node tmp = stack.pop();//得到的是中间节点，只不过有些是俩边都为null
//                System.out.print(tmp.val + " ");
                arr.add(tmp.val);
                cur = tmp.right;
            }
    }

    //是否是升序
    public Boolean isUP() {

        inOrder_getArr(root);

        List<Integer> tmp = arr;
        int i = 0;
        while (tmp != null && i + 1 < tmp.size()) {
            if (tmp.get(i) > tmp.get(i + 1)) {
                return false;
            }
            i++;
        }
        return true;
    }

    //判断黑色节点个数是否相同
    public Boolean IsBlackEqual(Node root) {
        int blackCount = 0;
        Node tmp = root;

        //根节点不为黑色
        if (this.root.color != COLOR.BLACK) {
            System.out.println("根节点不为黑色");
        }

        //得到一条支路的Black数量
        while (tmp != null) {
            if (tmp.color == COLOR.BLACK) {
                blackCount++;
            }
            tmp = tmp.left;
        }
        return isEqualInTree(root, 0, blackCount);
    }

    private Boolean isEqualInTree(Node root, int pathCount, int blackCount) {
        if (root == null) {
            return true;
        }
        if (root.color == COLOR.BLACK) {
            pathCount++;
        }

        Node tmp = root.parent;
        if (tmp != null && root.color == COLOR.RED && tmp.color == COLOR.RED) {
            System.out.println("俩个红色节点挨在了一起");
        }
        if (root.left == null && root.right == null) {
            if (pathCount != blackCount) {
                System.out.println("黑色节点不相同");
                return false;
            }
        }
        return isEqualInTree(root.left, pathCount, blackCount) &&
                isEqualInTree(root.right, pathCount, blackCount);
    }
}
